package DoExercise.JianzhiOffer;

/**
 * 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。
 * 要求不能创建任何新的结点，只能调整树中结点指针的指向。
 * <p>
 * 性质：二叉搜索树的中序遍历为递增序列 。
 * <p>
 * 1、二叉搜索树的中序遍历为递增序列 。
 * 2、构建相邻节点的引用关系时，设前驱节点为pre 和 当前节点为 cur，应该构建 pre.right = cur 和 cur.left = pre
 * 3、设头节点为 head、尾节点为 pre，应该构建 head.left = pre 和 pre.left = head;
 * <p>
 * https://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5?tpId=13&&tqId=11179&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
 */
public class Offer026_二叉搜索树与双向链表
{
    static Offer000_Common.TreeNode pre, head;
    
    public static void main(String[] args)
    {
        Offer000_Common.TreeNode node1 = new Offer000_Common.TreeNode(4);
        Offer000_Common.TreeNode node2 = new Offer000_Common.TreeNode(2);
        Offer000_Common.TreeNode node3 = new Offer000_Common.TreeNode(5);
        Offer000_Common.TreeNode node4 = new Offer000_Common.TreeNode(1);
        Offer000_Common.TreeNode node5 = new Offer000_Common.TreeNode(3);
        
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        
        Offer000_Common.TreeNode treeNode = Convert_1(node1);
        int x = 100;//头尾相连的链表加个结束条件
        while (treeNode != null && x >= 0)
        {
            System.out.println(treeNode.val);
            treeNode = treeNode.left;
            x--;
        }
    }
    
    
    public static Offer000_Common.TreeNode Convert_1(Offer000_Common.TreeNode pRootOfTree)
    {
        if (pRootOfTree == null) return null;
        dfsRecur(pRootOfTree);
        //所有顺序排好后，首位节点呼唤指向
        head.left = pre;
        pre.right = head;
        return head;
    }
    
    
    /**
     * 1 中序遍历结合题目要求可知：(1) pre.left = cur ; cur.right = pre (2) pre == null ; cur此时是头节点
     *
     * @param cur
     */
    private static void dfsRecur(Offer000_Common.TreeNode cur)
    {
        if (cur == null) return;
        dfsRecur(cur.left);
        if (pre != null)
        {
            pre.right = cur;
        } else
        {
            head = cur;
        }
        cur.left = pre;
        pre = cur;
        dfsRecur(cur.right);
    }
    
    
}
